#include <cstdio>
#include <cstdlib>
#include <cmath>

int myPow(int base, int pow)
{
	if (pow == 0)
	{
		return 1;
	}
	if (pow == 1)
	{
		return base;
	}
	int tmp = myPow(base, pow / 2);
	return  tmp * tmp * (pow % 2 ? base : 1);
}
int FunCmp(const void* pLeft, const void* pRight)
{
	int* pDataLeft = (int*)pLeft;
	int* pDataRight = (int*)pRight;

	return *pDataLeft - *pDataRight;
}

int Majority1(int* data, int num)
{
	qsort(data, num, sizeof(int), FunCmp);
	return data[(num/2)];
}

int Majority2(int* data, int left, int right)
{
	if (left >= right)
	{
		return data[left];
	}
	int mid = (left + right)/2;
	int lval = Majority2(data, left, mid);
	int rval = Majority2(data, mid+1, right);
	if (lval == rval)
	{
		return lval;
	}
	else if (lval < rval)
	{
		return lval;
	}
	else
	{
		return rval;
	}
}

int main(int argc, char **argv)
{
	//int base = 2;
	//int pow = 20;
	//printf("%d^%d=%d\n", base, pow, myPow(base, pow));

	int data[] = {1, 3, 3, 2, 3};

	int m = Majority2(data, 0, sizeof(data)/sizeof(data[0]) - 1);
	printf("Majority is %d\n", m);
	return 0;
}